package com.yuqingsong.algorithm.heap;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;

import com.yuqingsong.algorithm.sort.AbstractSort;

/**
 * 堆数据结构
 * 
 * @author Administrator
 * 
 */
public class Heap<T> extends AbstractSort<T>{


	private T[] array;
	/**
	 * @param array 以数组形式存储堆元素
	 * @param c 用于比较堆中的元素。c.compare(根,叶子) > 0。 使用相反的Comparator可以创建最大堆、最小堆。
	 */
	public Heap(T[] array, Comparator<? super T> c) {
		init( c);
		this.array = array;
		if(this.array != null){
			buildHeap();
		}
	}

	/**
	 * 返回值为i/2
	 * 
	 * @param i
	 * @return
	 */
	private int parent(int i) {
		return (i - 1) >> 1;
	}

	/**
	 * 返回值为2*i
	 * 
	 * @param i
	 * @return
	 */
	private int left(int i) {
		return ((i + 1) << 1) - 1;
	}

	/**
	 * 返回值为2*i+1
	 * 
	 * @param i
	 * @return
	 */
	private int right(int i) {
		return (i + 1) << 1;
	}

	/**
	 * 堆化
	 * 
	 * @param i
	 *           堆化的起始节点
	 */
	private void heapify(int i) {
		heapify(i, array.length);
	}

	/**
	 * 堆化，
	 * 
	 * @param i
	 * @param size
	 *           堆化的范围
	 */
	private void heapify(int i, int size) {
		int l = left(i);
		int r = right(i);
		int next = i;
		if (l < size && comp.compare(array[l], array[i]) > 0)
			next = l;
		if (r < size && comp.compare(array[r], array[next]) > 0)
			next = r;
		if (i == next)
			return;
		swap(this.array,i, next);
		heapify(next, size);
	}

	/**
	 * 对堆进行排序
	 */
	public T[] sort() {
		// buildHeap();
		for (int i = array.length - 1; i > 0; i--) {
			swap(this.array,0, i);
			heapify(0, i);
		}
		return array;
	}


	/**
	 * 创建堆
	 */
	private void buildHeap() {
		for (int i = (array.length) / 2 - 1; i >= 0; i--) {
			heapify(i);
		}
	}

	/**
	 * 设置根节点，并保持堆特性
	 * 
	 * @param root
	 */
	public void setRoot(T root) {
		array[0] = root;
		heapify(0);
	}

	@Override
	public int hashCode() {
		return array.hashCode();
	}

	@Override
	public boolean equals(Object obj) {
		if (obj instanceof Heap<?>) {
			return Arrays.equals(array, ((Heap<?>) obj).array);
		}
		return false;
	}

	public T root() {
		return array[0];
	}

	/**
	 * 删除根节点
	 * 
	 * @return 堆的根节点
	 */
	public T removeRoot() {
		if (array.length == 0) {
			throw new IllegalArgumentException("can not extract max element in empty heap");
		}
		T max = array[0];
		int len = array.length - 1;
		@SuppressWarnings("unchecked")
		// 使用了反射，有可能会影响效率
		T[] newHeap = (T[]) Array.newInstance(max.getClass(), len);
		array[0] = array[len];
		System.arraycopy(array, 0, newHeap, 0, newHeap.length);
		array = newHeap;
		heapify(0);
		return max;
	}

	/**
	 * 将T插入到堆中
	 * 实现思路：
	 * 1：增加heap大小，将t添加到队尾
	 * 2：如果t比parent(t)大，交换位置
	 * 3：将t置为parent(t),重复步骤2，循环到根节点。
	 * @param t
	 */
	public void insert(T t) {
		int len = array.length + 1;
		@SuppressWarnings("unchecked")
		T[] newHeap = (T[]) Array.newInstance(t.getClass(), len);
		System.arraycopy(array, 0, newHeap, 0, array.length);
		newHeap[len - 1] = t;
		array = newHeap;
		for (int i = len - 1, parentIndex = parent(i); i > 0 && comp.compare(array[i], array[parentIndex]) > 0;) {
			swap(this.array,i, parentIndex);
			i = parentIndex;
			parentIndex= parent(i);
		}
	}
	
	public String toString(){
		if(array!=null){
			StringBuilder sb = new StringBuilder();
			int lever = 2;
			sb.append(array[0]);
			for(int i = 1;i<array.length;i++){
				if(i == lever -1){
					sb.append("\r\n");
					lever<<=1;
				}else{
					sb.append(",");
				}
				sb.append(array[i]);
			}
			return sb.toString();
		}
		return "Empty Heap";
	}
	
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Integer[] temp = null;
		temp = new Integer[] { 5, 2, 4, 6, 1, 3, 2, 6 };
		temp = new Integer[] { 16, 14, 8, 7, 9, 3, 2, 4, 1 };

		Comparator<Integer> comp = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		};
		// 创建最大堆
		Heap<Integer> heap = new Heap<Integer>(temp, comp);
		// heap.buildHeap();
		for (int i : temp) {
			System.out.print(i + " ");
		}
		System.out.println();

//		heap.sort();
		for (int i : temp) {
			System.out.print(i + " ");
		}
		System.out.println();
		System.out.println(2<<1);
		System.out.println(heap);
	}

	@Override
	public T[] sort(T[] array) {
		T[] arrayBak = this.array;
		this.array = array;
		buildHeap();
		T[] sort = this.sort();
		this.array = arrayBak;
		return sort;
	}

}
